/**
 * @author LKQ
 * @date 2022/2/19 20:07
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5))),
                l2 = new ListNode(1, new ListNode(3, new ListNode(4))),
                l3 = new ListNode(2, new ListNode(6));
        ListNode[] listNodes = {l1, l2, l3};
        solution.mergeKLists(listNodes);
    }

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(-10000);
        if (lists == null || lists.length == 0) {
            return null;
        }
        for (ListNode list : lists) {
            while (list != null) {
                dummy = insert(dummy, new ListNode(list.val));
                list = list.next;
            }
        }
        return dummy.next;
    }
    public ListNode insert(ListNode head, ListNode insertNode) {
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        while (true) {
            if (insertNode.val > head.val && head.next == null) {
                head.next = insertNode;
                break;
            }else if (insertNode.val > head.val) {
                pre = head;
                head = head.next;
            }else {
                pre.next = insertNode;
                insertNode.next = head;
                break;
            }
        }
        return dummy.next;
    }
}
